import java.awt.*;
import java.math.BigInteger;
import java.util.*;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-04-12
 * Time: 20:18
 */
public class Test3 {

    //-------------------------------------------Day21-----------------------------------------------
    // No.1 有点投机取巧。嘻嘻
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int groups = scanner.nextInt();

        for (int i = 0; i < groups; i++) {
            // n个数
            int n = scanner.nextInt();
            List<Integer> list = new LinkedList<>();
            // 洗牌k次
            int k = scanner.nextInt();
            // 填充牌
            for (int j = 0; j < 2 * n; j++) {
                int x = scanner.nextInt();
                list.add(x);
            }
            // 洗牌
            while (k != 0) {
                int cur = 1; // 插入位置
                int index = n;// 待插入数值
                while (cur < n * 2) {
                    list.add(cur, list.get(index));
                    cur += 2;
                    index += 2;
                }
                k--;
            }
            for (int j = 0; j < 2 * n; j++) {
                System.out.print(list.get(j) + " ");
            }
            System.out.println();

        }

    }

    // No.2 这种代码优点冗余
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int songNums = scanner.nextInt();
        scanner.nextLine();// 吃空格
        String order = scanner.nextLine();

        int cur = 1;
        int end = cur + 3;
        int start = 1;
        if (songNums <= 4) {
            for (int i = 0; i < order.length(); i++) {
                if (cur == 1 && order.charAt(i) == 'U') {
                    cur = songNums;
                } else if (cur == songNums && order.charAt(i) == 'D') {
                    cur = 1;
                } else if (order.charAt(i) == 'U') {
                    cur--;
                } else {
                    cur++;
                }
            }
            for (int i = 1; i <= songNums; i++) {
                System.out.print(i + " ");
            }
            System.out.println();
            System.out.println(cur);
        } else {
            for (int i = 0; i < order.length(); i++) {
                if (cur == 1) {
                    if (order.charAt(i) == 'U') {
                        cur = songNums;
                        end = songNums;
                        start = end - 3;
                    } else {
                        cur++;
                    }

                } else if (cur == songNums) {
                    if (order.charAt(i) == 'D') {
                        cur = 1;
                        start = 1;
                        end = start + 3;
                    } else {
                        cur--;
                    }
                } else if (order.charAt(i) == 'U') {
                    cur--;
                } else if (order.charAt(i) == 'D') {
                    cur++;
                }

                if (cur > end) {
                    end++;
                    start++;
                }
                if (cur < start) {
                    start--;
                    end--;
                }
            }
            for (int i = start; i <= end; i++) {
                System.out.print(i + " ");
            }
            System.out.println();
            System.out.println(cur);
        }

    }

    //-------------------------------------------Day22-----------------------------------------------
    // No.1:这题写过，博哥讲过，bug点【返回-1】
    public static void main3(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入
        String str = scanner.nextLine();
        // 第一次遍历str字符：构建下标数组
        int[] array = new int['z'];
        for (int i = 0; i < str.length(); i++) {
            // 简化下标
            int index = str.charAt(i) - 'a';
            array[index]++;
        }
        // 二次遍历array数组，找到第一次只出现一次的字符
        for (int i = 0; i < str.length(); i++) {
            int index = str.charAt(i) - 'a';
            if (array[index] == 1) {
                char result = (char) (index + 'a');
                System.out.println(result);
                return;
            }
        }
        System.out.println(-1);

    }

    // No.2:bug点【多组输入】
    public static int maxDivisor(int bi, int c) {
        while (bi % c != 0) {
            int tmp = bi;
            bi = c;
            c = tmp % c;
        }
        return c;
    }

    public static void main4(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            // 怪物数量
            int n = scanner.nextInt();
            // 当前角色能值
            int c = scanner.nextInt();
            // 每只怪物的防御值
            for (int i = 0; i < n; i++) {
                int bi = scanner.nextInt();
                if (bi <= c) {
                    c += bi;
                } else {
                    c += maxDivisor(bi, c);

                }
            }
            System.out.println(c);
        }
    }

//    public static void main(String[] args) {
//        System.out.println(maxDivisor(100,105));
//    }

    //-------------------------------------------Day23-----------------------------------------------
    // No.1
    public int getValue(int[] gifts, int n) {
        Arrays.sort(gifts);
        //初始化候选人和他们的计票
        int maxCount = 0;
        int dest = 0;
        int cur = gifts[0];

        int i = 0;
        // 遍历数组，找多数元素
        while (i < n) {
            // 初始临时长度为len
            int len = 0;
            while (i < n && gifts[i] == cur) {
                len++;
                i++;
            }
            // len>maxCount,更新maxCount.可能目标值dest
            if (len > maxCount) {
                dest = cur;
                maxCount = len;
            }
            // 更新cur比对值
            if (i < n && gifts[i] != cur) {
                cur = gifts[i];
            }
        }
        if (maxCount > n / 2) {
            return dest;
        }
        return 0;
    }

    // No.2:不会写！！！
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        // 输入
//        String str1 = scanner.nextLine();
//        String str2 = scanner.nextLine();
//
//        // str1中是较长字符串
//        if (str1.length()<str2.length()) {
//            String strTmp = str1;
//            str1 = str2;
//            str2 = strTmp;
//        }
//
//        List<Character> list1 = new ArrayList<>();
//        List<Character> list2 = new ArrayList<>();
//
//        for (int i = 0; i < str1.length(); i++) {
//            list1.add(str1.charAt(i));
//        }
//        for (int i = 0; i < str2.length(); i++) {
//            list2.add(str2.charAt(i));
//        }
//        Collections.sort(list1);
//        Collections.sort(list2);
//
//        // 计算Levenshtein距离
//        // 1.需要增加或删除的步骤
//        int deleteCount = list1.size()- list2.size();
//
//        // 2.需要替换的步骤
//        int index = 0;
//        int updateCount = 0;
//        while (index< list2.size()) {
//            if (list2.get(index)!=list1.get(index)) {
//                updateCount++;
//            }
//            index++;
//        }
//        int total = deleteCount+updateCount;
//        System.out.println(total);
//
//
//
//    }

    //-------------------------------------------Day24-----------------------------------------------、
    // No.1
    // 年终奖：这题大佬的思想很强！！！
    public int getMost(int[][] board) {
        // 特殊情况处理
        if (board == null || board.length == 0) {
            return 0;
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (i == 0 && j == 0) {
                    // 奖金就是第一个格子本身
                } else if (i == 0) {
                    // 说明在第一行   第一行的奖金只能来自第一行左边的格子
                    // 奖金等于当前格子的奖金加上左边格子的奖金
                    board[0][j] += board[0][j - 1];
                } else if (j == 0) {
                    // 说明在第一列   第一列的奖金只能来自列的上面个格子
                    // 奖金等于当前格子的奖金加上上面格子的奖金
                    board[i][0] += board[i - 1][0];
                } else {
                    // 来自上面或者左边的格子，选取最大奖金的。
                    // 最大奖金等于当前格子奖金加上左边或上面格子中奖金数大的那个
                    board[i][j] += Math.max(board[i][j - 1], board[i - 1][j]);
                }
            }
        }

        // 增加通用型，直接用数据的长度吧
        return board[board.length - 1][board[0].length - 1];

    }

    // No.2:迷宫问题，好像要使用回溯算法，dfs，挺难的


    //-------------------------------------------Day25-----------------------------------------------
    // No.1：错解
//    public static int digit(int x) {
//        int count = 0;
//        while (x!=0) {
//            count++;
//            x/=10;
//        }
//        return count;
//    }
//    public static void print(int T,int x) {
//        if (T>1) {
//            print(T-1,x/10);
//        }
//        System.out.print(x%10);
//    }
//    public static void main(String[] args) {
//
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNextInt()) {
//            int n = scanner.nextInt();
//
//            int cur00 = 1;
//            int cur01 = 1;
//            int cur10 = 1;
//            int cur11 = 0;
//
//
//            for (int i = 0; i < n; i++) {
//                int result00 = 1;
//                int result01 = 1;
//                int result10 = 1;
//                int result11 = 0;
//                int x = scanner.nextInt();
//                for (int j = 1; j < x; j++) {
//                    int tmp00 = result00;
//                    int tmp01 = result01;
//                    int tmp10 = result10;
//                    int tmp11 = result11;
//
//                    result00 = tmp00*cur00 + tmp01*cur10;
//                    result01 = tmp00*cur01 + tmp01*cur11;
//                    result10 = tmp10*cur00 + tmp11*cur10;
//                    result11 = tmp10*cur01 + tmp11*cur11;
//
////                    int tmp00 = cur00;
////                    cur00 = cur00 * cur00 + cur01 * cur10;
////                    int tmp01 = cur01;
////                    cur01 = cur01 * tmp00 + cur01 * cur11;
////                    int tmp10 = cur10;
////                    cur10 = cur10 * tmp00 + cur11 * tmp01;
////
////                    cur11 = tmp10 * tmp01 + cur11 * cur11;
//
//                }
//                if (digit(result00) <= 4) {
//                    int sub = 4 - digit(result00);
//                    for (int j = 0; j < sub; j++) {
//                        System.out.print(0);
//                    }
//                    System.out.print(result00);
//                } else {
//                    print(4,result00);
//                }
//            }
//        }
//    }

    // No.1：正解 满足斐波那契规律1 2 3 5 8 。。。
    // 由于只考虑后四位，取%10000
    public static void makeKey(int[] array) {
        array[1] = 1;
        array[2] = 2;
        // 为了方便之后查询密码，这里提前构造
        for (int i = 3; i < 10001; i++) {
            array[i] = (array[i - 1] + array[i - 2]) % 10000;
        }

    }

    public static void main15(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] array = new int[10001];
        // 构造密码数组array
        makeKey(array);
        // 输入
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; i++) {
                // x表示次方
                int x = scanner.nextInt();
                System.out.printf("%04d", array[x]);
            }
            System.out.println();
        }
    }


    // No.2 : 树根问题
    public static int getTreeRoot(String n) {
        // 计算树根
        int sum = 0;
        for (int i = 0; i < n.length(); i++) {
            sum += n.charAt(i) - '0';
        }
        if (sum > 9) {
            n = String.valueOf(sum);
            return getTreeRoot(n);
        } else {
            return sum;
        }

    }

    public static void main16(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入(由于数字范围太大，所以以字符串的形式输入)
        while (scanner.hasNextLine()) {
            String n = scanner.nextLine();
            System.out.println(getTreeRoot(n));
        }

    }

    //-------------------------------------------Day26-----------------------------------------------
    // No.1:青蛙跳台阶II，次方问题？
    public static int jumpFloorII(int number) {
        // write code here
        if (number > 1) {
            return 2 * jumpFloorII(number - 1);
        } else {
            return number;
        }

    }

    public static void main17(String[] args) {
        System.out.println(jumpFloorII(2));
    }

    // No.2:简单
    public static void main18(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextDouble()) {
            double n = scanner.nextDouble();
            double r = scanner.nextDouble();
            double pi = 3.14;
            double circleLen = 2 * pi * r;
            if (circleLen < n) {
                System.out.println("No");
            } else {
                System.out.println("Yes");
            }
        }
    }

    //-------------------------------------------Day27-----------------------------------------------
    // No.1:不用加减乘除做加法
    public int Add(int num1, int num2) {
        // 首先只考虑加法不考虑进位：相当于异或^
        int add = num1 ^ num2;
        // 只考虑进位：相当于按位与&
        int carry = num1 & num2;
        while (carry != 0) {
            int tmp = add;
            // 进位
            carry = carry << 1;
            // 相加
            add = add ^ carry;
            // 新的进位数
            carry = tmp & carry;
        }
        return add;
    }

    // No.2:三角形
    public static void main19(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // while条件中和下面输入的要匹配！！！
        while (scanner.hasNextBigInteger()) {
            BigInteger a = scanner.nextBigInteger();
            BigInteger b = scanner.nextBigInteger();
            BigInteger c = scanner.nextBigInteger();
            if ((a.add(b)).compareTo(c) > 0 && (a.add(c)).compareTo(b) > 0 && (b.add(c)).compareTo(a) > 0) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
    }

    //-------------------------------------------Day28-----------------------------------------------
    // No.1 24???
    public static void main20(String[] args) {
        int i = 5;
        int s = (i++) + (++i) + (i--) + (--i);
        System.out.println(s);
    }

    // No.2:猴子分桃:找的题解！！！
    public static void main21(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            long minCount = (long) Math.pow(5, n) - 4;
            long older = (long) Math.pow(4, n) + n - 4;
            System.out.print(minCount + " ");
            System.out.println(older);
        }
    }

    // No.3
    static class Node {
        int val;
        Node next;

        public Node(int value) {
            this.val = value;
        }
    }

    public static void main22(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node head = null;
        Node cur = head;
        // 构造链表
        for (int i = 0; i < n; i++) {
            if (head == null) {
                head = new Node(scanner.nextInt());
                cur = head;
            } else {
                cur.next = new Node(scanner.nextInt());
                cur = cur.next;
            }
        }
        // 输入范围
        int l = scanner.nextInt() - 1;
        int r = scanner.nextInt() - 1;
        // 找到 start 结点
        Node prevStart = head;
        Node start = head;

        if (l == 0) {
            start = head;
        } else {
            while (l - 1 != 0) {
                prevStart = prevStart.next;
                l--;
            }
            start = prevStart.next;
        }


        // 找到 end 结点位置
        Node end = head;
        while (r != 0) {
            end = end.next;
            r--;
        }
        // 在star到end范围内进行头插
        cur = start.next;
        Node endless = end.next;
        Node tmpStart = start;
        while (cur != endless) {
            // 循环终止条件：反转完end结点
            Node curNext = cur.next;
            cur.next = tmpStart;
            tmpStart = cur;
            cur = curNext;
        }
        // 如果起始start==head，直接更新头即可
        if (start == head) {
            head = end;
        } else {
            // 否则让头节点指向end结点
            prevStart.next = end;
        }
        // start此时指向范围内的尾部，直接让他的下一个节点指向余下部分即可
        start.next = endless;

        // 打印结果
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

    //-------------------------------------------Day29-----------------------------------------------

    // write your code here
    // No.1:找出假币 有一点疑问：为什么我看题解，每次要分成3份？
    public static void main23(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (true) {
            int n = scanner.nextInt();
            if (n == 0) {
                break;
            }
            // 计数器
            int count = 0;
            while (n >= 2) {
                count++;
                if (n % 3 == 0) {
                    //不可以整除则取最差情况：特别的一份是 n/3 + 1个金币
                    n = n / 3 + 1;
                } else {
                    //可以整除在直接整除，能够获取到一份
                    n /= 3;
                }
            }
            System.out.println(count);
        }
    }


    // No.2
//
//    public int getFirstUnFormedNum(int[] arr) {
//        // 排序
//        Arrays.sort(arr);
//        int min = arr[0];
//        int max = 0;
//        for (int i = 0; i < arr.length; i++) {
//            max += arr[i];
//        }
//        int sum = (arr.length*(arr[0]+arr[arr.length-1]))/2;
////        if (sum==max) {
////            if (arr[0]==1) {
////                return max+1;
////            } else {
////                return max-1;
////            }
////        }
//
//        return 1;
//    }




    //-------------------------------------------Day30-----------------------------------------------
    // No.1
    public static void main24(String[] args) {
        Integer i01 = 59;
        int i02 = 59;
        Integer i03 = Integer.valueOf(59);
        Integer i04 = new Integer(59);
        System.out.println(i03 == i04);// false
        System.out.println(i02 == i04);// true
        System.out.println(i01 == i04);// false
    }

    // No.2 求质因数
    public static void main25(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int count = 0;
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    while (n % i == 0) {
                        n /= i;
                    }
                    count++;
                }
            }
            if (n != 1) {
                count++;
            }
            System.out.println(count);
        }
    }

    // No.3 最难的问题
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) {
            String password = in.nextLine();
            for (int i = 0; i < password.length();i++) {
                char ch = password.charAt(i);
                if (!Character.isSpaceChar(ch)) {
                    int x = ch-5-'A';
                    if (x<0) {
                        x+=26;
                    }
                    char tmp = (char)(x+'A');
                    System.out.print(tmp);
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println();

        }
    }

}

